`
https://leetcode.cn/problems/implement-trie-prefix-tree/
`

// 前缀树结点
class TrieNode {
  constructor() {
    this.val = null
    // 题目只会出现小写字母
    this.chilren = new Array(26).fill(null)
  }
}

// 前缀树
class Trie {
  constructor() {
    this.root = new TrieNode()
  }

  /** 
  * @param {string} word
  * @return {void}
  */
  insert(word) {
    this._insert(this.root, word, 0)
  }
  _insert(node, word, i) {
    if (!node) node = new TrieNode()
    if (i === word.length) {
      node.val = word
      return node
    }
    const idx = word.charCodeAt(i) - 'a'.charCodeAt(0)
    node.chilren[idx] = this._insert(node.chilren[idx], word, i + 1)
    return node
  }
  /** 
  * @param {string} word
  * @return {boolean}
  */
  search(word) {
    const x = this.getNode(word)
    if (!x || !x.val) return false
    return true
  }

  /** 
  * @param {string} prefix
  * @return {boolean}
  */
  startsWith(prefix) {
    return this.getNode(prefix) !== null
  }

  // 从节点 node 开始搜索 key，如果存在返回对应节点，否则返回 null
  getNode(key) {
    // 从根节点开始搜索
    let p = this.root
    for (let i = 0; i < key.length; i++) {
      // 如果遇到 null，说明找不到
      if (!p) return null
      // 拿到对应的字符的下标
      const idx = key.charCodeAt(i) - 'a'.charCodeAt(0)
      // 进入字符对应的下一层节点
      p = p.chilren[idx]
    }
    return p
  }
}

/** 
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/